home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / benchmarks / itc / sld / RCS / bsearch.c,v < prev    next >
Encoding:
Text File  |  1992-05-12  |  2.5 KB  |  129 lines
  1. head     1.2;
  2. branch   ;
  3. access   ;
  4. symbols  ;
  5. locks    ; strict;
  6. comment  @ * @;
  7.  
  8.  
  9. 1.2
  10. date     92.05.12.15.00.58;  author kupfer;  state Exp;
  11. branches ;
  12. next     1.1;
  13.  
  14. 1.1
  15. date     92.05.12.14.50.31;  author kupfer;  state Exp;
  16. branches ;
  17. next     ;
  18.  
  19.  
  20. desc
  21. @ANSI bsearch routine.
  22. @
  23.  
  24.  
  25. 1.2
  26. log
  27. @Don't assume <stdlib.h> exists in non-ANSI environments.
  28. @
  29. text
  30. @/* 
  31.  * bsearch.c --
  32.  *
  33.  *    Source code for the bsearch library routine.
  34.  *
  35.  * Copyright 1989 Regents of the University of California
  36.  * Permission to use, copy, modify, and distribute this
  37.  * software and its documentation for any purpose and without
  38.  * fee is hereby granted, provided that the above copyright
  39.  * notice appear in all copies.  The University of California
  40.  * makes no representations about the suitability of this
  41.  * software for any purpose.  It is provided "as is" without
  42.  * express or implied warranty.
  43.  * 
  44.  * $Sprite: /sprite/src/lib/c/stdlib/RCS/bsearch.c,v 1.4 89/05/18 17:09:12 rab Exp 
  45.  */
  46.  
  47. #ifndef lint
  48. static char rcsid[] = "$Header: /sprite/src/benchmarks/itc/sld/RCS/bsearch.c,v 1.1 92/05/12 14:50:31 kupfer Exp Locker: kupfer $";
  49. #endif /* not lint */
  50.  
  51.  
  52. #ifdef __STDC__
  53. #include <stdlib.h>
  54. #endif
  55.  
  56. #include <stdio.h>
  57. #include <sys/types.h>
  58.  
  59. #ifndef __STDC__
  60. #define const   /**/
  61. #endif
  62.  
  63.  
  64. /*
  65.  *----------------------------------------------------------------------
  66.  *
  67.  * bsearch --
  68.  *
  69.  *    Bsearch searches base[0] to base[n - 1] for an item that
  70.  *      matches *key.  The function cmp must return negative if its first
  71.  *      argument (the search key) is less that its second (a table entry),
  72.  *      zero if equal, and positive if greater.  Items in the array must
  73.  *      be in ascending order.  
  74.  *
  75.  * Results:
  76.  *    Returns a pointer to a matching item, or NULL if none exits.
  77.  *
  78.  * Side effects:
  79.  *    None.
  80.  *
  81.  *----------------------------------------------------------------------
  82.  */
  83.  
  84. char *
  85. bsearch(key, base, n, size, cmp)
  86.     const char *key;
  87.     const char *base;
  88.     size_t n;
  89.     size_t size;
  90. #ifdef __STDC__
  91.     int (*cmp)(const void *, const void *);
  92. #else
  93.     int (*cmp)();
  94. #endif
  95. {
  96.     const char *middle;
  97.     int c;
  98.  
  99.  
  100.     for (middle = base; n != 0;) {
  101.     middle += (n/2) * size;
  102.     if ((c = (*cmp)(key, middle)) > 0) {
  103.         n = (n/2) - ((n&1) == 0);
  104.         base = (middle += size);
  105.     } else if (c < 0) {
  106.         n /= 2;
  107.         middle = base;
  108.     } else {
  109.         return (char *) middle;
  110.     }
  111.     }
  112.     return NULL;
  113. }
  114.  
  115. @
  116.  
  117.  
  118. 1.1
  119. log
  120. @Initial revision
  121. @
  122. text
  123. @d19 1
  124. a19 1
  125. static char rcsid[] = "$Header: /sprite/src/lib/c/stdlib/RCS/bsearch.c,v 1.4 89/05/18 17:09:12 rab Exp $";
  126. d23 1
  127. d25 1
  128. @
  129.